package com.fengkai.filepost.pdfoutstream.test.ODsolutions;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

/**
 * @author Fengkai
 * @creat 2023/4/17
 * 每个小桶装的小球数量记录在数组 bucketBallNums 中,游戏开始时，要求所有桶的小球总数不能超过 SUM，
 * 如果小球总数超过 SUM，则需对所有的小桶统一设置一个容量最大值 maxcapacity并需将超过容量最大值的小球拿出来，直至小桶里的小球数量小于 maxcapacity;
 * 请您根据输入的数据，计算从每个小桶里拿出的小球数量，
 * 限制规则一:
 * 所有所有小桶的小球总和小于 SUM，则无需设置容量值，并且无需从小桶中拿球出来，返回结果[];
 * 限制规则二:
 * 如果所有小桶的小球总和大于 SUM，则需设置容量最大值 maxcapacity并且需从小桶中拿球出来，返回从每个小桶拿出的小球数量组成的数组;
 * 输入描述
 * 第一行输入2个正整数，数字之间使用空格隔开，其中第一个数字表示 SUM ，第二个数字表示 bucketBallNums 数组长度:第二行输入N个正整数，数字之间使用空格隔开，
 * 表示 bucketBallNums 的每一项:
 * 输出描述
 * 从每个小桶里拿出的小球数量。
 * 示例一
 * 输入
 * 14 7
 * 2 3 2 5 5 1 4
 * 输出
 * [0,1,0,3,3,0,2]
 * 说明
 * 小球总数为 22，sum=14，超出范围了，需从小桶取球，
 * maxCapacity=1，取出球后，桶里剩余小球总和为7，远小于 14 maxCapacity=2，取出球后，桶里剩余小球总和为13
 * maxCapacity=3，取出球后，桶里剩余小球总和为 16，大于14因此 maxCapacity为2，每个小桶小球数量大于2的都需要拿出来;
 */
public class KaiFangRiHuodong {
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int sum = scanner.nextInt();
        int n = scanner.nextInt();
        int[] ints = new int[n];
        for (int i = 0; i < n; i++) {
            ints[i] = scanner.nextInt();
        }
        System.out.println(Arrays.toString(kaiFangRiHuodong(sum, ints)));

    }

    public static int[] kaiFangRiHuodong (int sum, int[] bucketBallNums) {

        int length = bucketBallNums.length;
        int[] result = new int[length];
        int sumA = 0;
        for (int bucketBallNum : bucketBallNums) {
            sumA += bucketBallNum;
        }

        if (sumA <= sum) {
            return new int[0];
        }
        int[] originInts = Arrays.copyOf(bucketBallNums, length);
        Arrays.sort(bucketBallNums);
        //二分法
        int target = sum / length; //每个值要小于等于target
        int max = bucketBallNums[length - 1];

        for (int i = 0; i < length; i++) {
           result[i] = originInts[i] > target ? originInts[i] - target : 0;
        }
        while (max > target + 1) {
            int mid = (max + target) / 2;
            int total = sumA;
            int[] temp = new int[length];
            for (int i = 0; i < length; i++) {
                int put = originInts[i] > mid ? originInts[i] - mid : 0;
                total -= put;
                temp[i] = put;
            }

            if (total > sum) {
                max = mid;
            } else if (total < sum) {
                target = mid;
                result = temp;
            } else {
                result = temp;
                break;
            }
        }
        return result;
    }
}
